package org.chengn.level_middle.context1631;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @Title: Context1631
 * @Author ChengN
 * @Package org.chengn.level_middle.context1631
 * @Date 2023/12/11 21:42
 * @description: 最小体力消耗路径
 */
public class Context1631 {

    int[][] tmp = new int[100][100];
    final int[][] move = new int[][]{{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                tmp[i][j] = 0x3f3f3f3f;
            }
        }

        Queue<Point> queue = new ArrayDeque<>();
        queue.add(new Point(0, 0));
        tmp[0][0] = 0;

        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; ++i) {
                int pointX = point.x + move[i][0];
                int pointY = point.y + move[i][1];
                if (pointX >= 0 && pointX < m && pointY >= 0 && pointY < n) {
                    int val = Math.abs(heights[pointX][pointY] - heights[point.x][point.y]);
                    int temp = Math.max(val, tmp[point.x][point.y]);
                    if (temp < tmp[pointX][pointY]) {
                        tmp[pointX][pointY] = temp;
                        queue.add(new Point(pointX, pointY));
                    }
                }
            }
        }

        return tmp[m - 1][n - 1];

    }

    static class Point{
        public int x;
        public int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
